package com.ly;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author LY
 * @date 2022年04月23日 17:54
 * @project test
 */
public class Solution {
    public static void main(String[] args) {
//        ["apple","iOS","dog","nana","man","good","goodman","dognana"]
        String[] words = {"apple","iOS","dog","nana","man","good","goodman","dognana"};
        Solution solution = new Solution();
        String s = solution.longestWord(words);
        System.out.println(s);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param words string字符串一维数组
     * @return string字符串
     */
    public String longestWord (String[] words) {
        //1.判空
        if(words==null || words.length==0){
            return "";
        }
        //2.长度 字典顺序 排序
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o2.length()!=o1.length()){
                    return o2.length()-o1.length();

                }else {
                    return o1.compareTo(o2);
                }
            }
        });
        //3.构造map
        HashMap<String, Boolean> map = new HashMap<>();
        for (String w :words){
            map.put(w,null);
        }
        //4.遍历字符数组
        for (String w :words){
            if(canBuildWord(w,true,map)){
                return w;
            }
        }
        return "";
    }
    //5.编写合成字符串判断函数
    public boolean canBuildWord(String w, boolean first, Map<String,Boolean> map){
        if (map.containsKey(w)&&!first){
            return true;
        }
        for (int i=0;i<w.length();i++){
            String left = w.substring(0,i);
            String right = w.substring(i);
            if (map.containsKey(left)&&canBuildWord(right,false,map)){
                return true;
            }
        }
        return false;
    }

}
